package Leetcode.sliding_window;

/**
 * @Author: kirito
 * @Date: 2024/3/29 14:54
 * @Description:
 *最少交换次数来组合所有的 1 II
 * 交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。
 *
 * 环形 数组是一个数组，可以认为 第一个 元素和 最后一个 元素 相邻 。
 *
 * 给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [0,1,0,1,1,0,0]
 * 输出：1
 * 解释：这里列出一些能够将所有 1 聚集在一起的方案：
 * [0,0,1,1,1,0,0] 交换 1 次。
 * [0,1,1,1,0,0,0] 交换 1 次。
 * [1,1,0,0,0,0,1] 交换 2 次（利用数组的环形特性）。
 * 无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。
 * 因此，需要的最少交换次数为 1 。
 * 示例 2：
 *
 * 输入：nums = [0,1,1,1,0,0,1,1,0]
 * 输出：2
 * 解释：这里列出一些能够将所有 1 聚集在一起的方案：
 * [1,1,1,0,0,0,0,1,1] 交换 2 次（利用数组的环形特性）。
 * [1,1,1,1,1,0,0,0,0] 交换 2 次。
 * 无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。
 * 因此，需要的最少交换次数为 2 。
 * 示例 3：
 *
 * 输入：nums = [1,1,0,0,1]
 * 输出：0
 * 解释：得益于数组的环形特性，所有的 1 已经聚集在一起。
 * 因此，需要的最少交换次数为 0 。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * nums[i] 为 0 或者 1
 */

public class minSwaps {
    public static void main(String[] args) {
        int[] arr = {0,1,0,1,1,0,0};
        System.out.println(minSwaps(arr));
    }

    /**
     * 首先不看环形数组的前提，只当作数组，要把所有的1放到一起，那可以看作1的个数为一个窗口全是1
     * 1.先遍历一次，然后计算1的次数 =》窗口大小
     * 2.窗口遍历，求出现0最少的次数
     *      此时再把环形数组这个条件考虑进去
     *      其实环形数组的话，就还是遍历n次呗，末尾就拼接到前面嘛。看作两个小数组
     *
     *
     * 一遍过！！！！！！！！！！！哎嗨嗨
     *9ms
     * @param nums
     * @return
     */
    public static int minSwaps(int[] nums) {
        int len = nums.length;
        int count_1 = 0;
        for (int i = 0; i < len; i++) {
//            count_1 += nums[i] == 1 ? 1 : 0;
            //这里只有1  0  所以直接加就好了，但是代码意思可能就不是那么好理解了
            count_1 += nums[i];
        }
        int window_0 = 0;
        for (int i = 0; i < count_1; i++) {
            window_0 += nums[i] == 0 ? 1 : 0;
//            window_0 += nums[i] & 1;  // 使用位运算检查nums[i]是否为0  1&1=1  0&1=0 好像不能用位运算
        }
        int res = window_0;
        for (int i = count_1; i < len + count_1; i++) {
            window_0 += nums[i % len] == 0 ? 1 : 0;
            window_0 -= nums[i - count_1] == 0 ? 1 : 0;
            res = Math.min(res, window_0);
        }
        return res;
    }

    /**
     * 2ms  为什么这个会比我的要快呢
     * 三元运算符太慢了吗？
     * @param nums
     * @return
     */
    public static int minSwaps2(int[] nums) {
//求所有的1的个数，然后就可以获得一个窗口的大小，求窗口内1最多的个数，窗口大小减去这个个数就是要交换的次数
        int n = nums.length;
        int i = 0;
        int winLen = 0;
        int ans = 0;
        for (i = 0; i < n; i++) {
            winLen += nums[i];
        }
        int count = 0;
        for (i = 0; i < winLen; i++) {
            count += nums[i];
        }
        ans = count;
        for (i = winLen; i < n; i++) {
            count = count + nums[i] - nums[i - winLen];
            if (count > ans) ans = count;
        }
        for (i = 0; i < winLen - 1; i++) {
            count = count + nums[i] - nums[n - winLen + i];
            if (count > ans) ans = count;
        }
        return winLen - ans;
    }
}
